package com.shuang.greed7;

import java.util.Arrays;
import java.util.stream.IntStream;

public class LargestSumAfterKNegations {
//    public int largestSumAfterKNegations(int[] nums, int k) {
//        if (nums.length == 1)
//            return nums[0];
//
//        // 排序：先把负数处理了
//        Arrays.sort(nums);
//
//        for (int i = 0; i < nums.length && k > 0; i++) { // 贪心点, 通过负转正, 消耗尽可能多的k
//            if (nums[i] < 0) {
//                nums[i] = -nums[i];
//                k--;
//            }
//        }
//
//        // 退出循环, k > 0 || k < 0 (k消耗完了不用讨论)
//        if (k % 2 == 1) { // k > 0 && k is odd：对于负数：负-正-负-正
//            Arrays.sort(nums); // 再次排序得到最小的正数
//            nums[0] = -nums[0];
//        }
//
//        int sum = 0;
//        for (int num : nums) { // 计算最大和
//            sum += num;
//        }
//        return sum;
//    }

    class Solution {
        //贪心：将数组尽可能小的负数变成正数，正数尽可能取小的变成负数
        public int largestSumAfterKNegations(int[] nums, int k) {
            //数组按照绝对值大小从大到小排序
            nums = IntStream.of(nums)
                    .boxed()
                    .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                    .mapToInt(Integer::intValue).toArray();


            //将数组尽可能大的负数变成正数
            for (int i = 0; i < nums.length && k > 0; i++){
                if (nums[i] < 0){
                    nums[i] = -nums[i];
                    k--;
                }
            }

            //负数全部变完之后k还有剩余且是奇数 那么就把尽可能小的正数变成负的
            if (k % 2 == 1){
                nums[nums.length - 1] = -nums[nums.length - 1];
            }

            //求和返回结果
            return Arrays.stream(nums).sum();
        }
    }
}
